package com.topInterview;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 合并K个升序链表 小根堆思想，
 *
 * @Author: huangzhigao
 * @Date: 2022/2/19 16:03
 */
public class Leecode23_MergeSortArr {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (ListNode node : lists) {
            if(node != null){
                priorityQueue.add(node);

            }
        }

        //建立虚拟节点
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!priorityQueue.isEmpty()) {
            ListNode poll = priorityQueue.poll();
            cur.next = new ListNode(poll.val);
            cur = cur.next;
            if(poll.next!=null){
                priorityQueue.add(poll.next);
            }
        }
        return dummy.next;
    }


    public class MyComparator implements Comparator<ListNode> {

        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
}
